/*
 * File:   heap.c
 * Author: aishwarya
 *
 * Created on March 12, 2011, 3:42 AM
 * Binary Heap - Implementation
 */

#include "heap.h"

void heap_swap(BINARY_HEAP *h, int i, int j) {
    int t;

    h->indexOf[h->handleAt[i]] = j;
    h->indexOf[h->handleAt[j]] = i;

    t = h->handleAt[i];
    h->handleAt[i] = h->handleAt[j];
    h->handleAt[j] = t;
}

/*
Maintain the MAX-HEAP property.
 */
void max_heapify(BINARY_HEAP *h, int i) {
    register int largest, l = LEFT(i), r = RIGHT(i);

    largest = (l <= h->heap_size &&
            h->_keycmpfn(&h->elements[h->e_size * h->handleAt[l]],
            &h->elements[h->e_size * h->handleAt[i]]) > 0) ? l : i;

    largest = (r <= h->heap_size &&
            h->_keycmpfn(&h->elements[h->e_size * h->handleAt[r]],
            &h->elements[h->e_size * h->handleAt[largest]]) > 0) ? r : largest;

    if (largest != i) {
        heap_swap(h, i, largest);
        max_heapify(h, largest);
    }
}

/*
Maintain the MIN-HEAP property.
 */
void min_heapify(BINARY_HEAP *h, int i) {
    register int smallest, l = LEFT(i), r = RIGHT(i);

    smallest = (l <= h->heap_size &&
            h->_keycmpfn(&h->elements[h->e_size * h->handleAt[l]],
            &h->elements[h->e_size * h->handleAt[i]]) < 0) ? l : i;

    smallest = (r <= h->heap_size &&
            h->_keycmpfn(&h->elements[h->e_size * h->handleAt[r]],
            &h->elements[h->e_size * h->handleAt[smallest]]) < 0) ? r : smallest;

    if (smallest != i) {
        heap_swap(h, i, smallest);
        min_heapify(h, smallest);
    }
}

/*
Copies MAX element of the heap to the variable pointed by *max.
 */
void heap_maximum(BINARY_HEAP *h, void *max) {
    if (h->heap_size < 1)
        return;
    else h->_datacpyfn(max, (void *) &h->elements[h->e_size * h->handleAt[1]]);
}

/*
Copies MIN element of the heap to the variable pointed by *min.
 */
void heap_minimum(BINARY_HEAP *h, void *min) {
    heap_maximum(h, min);
}

/*
Removes MAX element from the heap and copies it to *max.
 */
void heap_extract_max(BINARY_HEAP *h, void *min) {
    if (h->heap_size < 1)
        return;

    h->_datacpyfn(min, &h->elements[h->e_size * h->handleAt[1]]);

    h->indexOf[h->handleAt[h->heap_size]] = 1;
    h->indexOf[h->handleAt[1]] = 0;

    h->handleAt[1] = h->handleAt[h->heap_size];
    h->handleAt[h->heap_size] = 0;

    (h->heap_size)--;
    max_heapify(h, 1);
}

/*
Removes MIN element from the heap and copies it to *min.
 */
void heap_extract_min(BINARY_HEAP *h, void *min) {
    if (h->heap_size < 1)
        return;

    h->_datacpyfn(min, &h->elements[h->e_size * h->handleAt[1]]);

    h->indexOf[h->handleAt[h->heap_size]] = 1;
    h->indexOf[h->handleAt[1]] = 0;

    h->handleAt[1] = h->handleAt[h->heap_size];
    h->handleAt[h->heap_size] = 0;

    (h->heap_size)--;
    min_heapify(h, 1);
}

/*
Increases the key of an element.
 */
void heap_increase_key(BINARY_HEAP *h, int id, const void * n) {
    int i;

    /* Get index of the element whose key is to be decreased */
    i = h->indexOf[id];

    if (i < 1 || i > h->heap_size)
        return;

    while (i > 1 && h->_keycmpfn(&h->elements[h->e_size * h->handleAt[PARENT(i)]], n) < 0) {
        h->indexOf[h->handleAt[PARENT(i)]] = i;
        h->handleAt[i] = h->handleAt[PARENT(i)];
        i = PARENT(i);
    }

    h->handleAt[i] = id;
    h->indexOf[id] = i;
    h->_datacpyfn(&h->elements[h->e_size * id], n);
}

/*
Inserts an element in the maximum binary heap.
Additionally, Increases the size of the underlying array representing the heap if
nelements is already reached.
 */
void max_heap_insert(BINARY_HEAP *h, int id, const void * n) {
    int i = ++(h->heap_size);

    h->indexOf[id] = i;
    heap_increase_key(h, id, n);
}

/*
 * Decreases the key of an element.
 */
void heap_decrease_key(BINARY_HEAP *h, int id, const void * n) {
    int i;

    /* Get index of the element whose key is to be decreased */
    i = h->indexOf[id];

    if (i < 1 || i > h->heap_size)
        return;

    while (i > 1 && h->_keycmpfn(&h->elements[h->e_size * h->handleAt[PARENT(i)]], n) > 0) {
        h->indexOf[h->handleAt[PARENT(i)]] = i;
        h->handleAt[i] = h->handleAt[PARENT(i)];
        i = PARENT(i);
    }

    h->handleAt[i] = id;
    h->indexOf[id] = i;
    h->_datacpyfn(&h->elements[h->e_size * id], n);
}

/*
Inserts an element in the minimum binary heap.
Additionally, Increases the size of the underlying array representing the heap if
nelements is already reached.
 */
void min_heap_insert(BINARY_HEAP *h, int id, const void * n) {
    int i = ++(h->heap_size);

    h->indexOf[id] = i;
    heap_decrease_key(h, id, n);
}

/*
Cleans a HEAP, removing all the nodes.
 */
void heap_clean(BINARY_HEAP *h) {
    int i;

    if (h->elements != NULL) {
        if (h->_delnodefn)
            for (i = 1; i <= h->heap_size; i++)
                h->_delnodefn((void *) &h->elements[h->e_size * h->handleAt[i]]);
        free(h->elements);
        h->elements = NULL;
    }

    /*
        printf("\nindex: ") ;
        for (i=1; i<=h->nelements; i++) {
            printf("%d ", h->indexOf[i]) ;
        }

        printf("\nhandle: ") ;
        for (i=1; i<=h->nelements; i++) {
            printf("%d ", h->handleAt[i]) ;
        }
     */

    h->heap_size = 0;
    h->nelements = 0;
    h->e_size = 0;
}

/*
Initializes a BINARY_HEAP
 */
void heap_init(BINARY_HEAP *h, int initial_size, size_t e_size, KEYCMP k, DATACPY d, DELNODE n, PRINTNODE p) {
    h->_keycmpfn = k;
    h->_datacpyfn = d;
    h->_delnodefn = n;
    h->_printfn = p;

    h->heap_size = 0;

    h->e_size = e_size;
    h->nelements = initial_size;

    /* Allocate nelements+1 elements because index in C starts from 1 and
     * our heap starts from 1 */
    h->elements = (char *) malloc((h->nelements + 1) * h->e_size);

    /* An application object with identifier <id> is stored at index[id] in heap */
    h->indexOf = (int *) calloc((h->nelements + 1), sizeof (int));
    /* Index <i> in heap points to application object with identifier handle[i] */
    h->handleAt = (int *) calloc((h->nelements + 1), sizeof (int));
}
